A geometry engine is generally defined as a set of basic routines for processing integrated circuit geometry, and examples of some basic routines include Boolean operations (And, Or, AndNot), sizing operations (Grow and Shrink), and transformation operations (Translation, Rotation, and Mirroring). The geometry engine is particularly suited to VLSI design for checking design rules and fracturing the integrated circuit layout.
Some examples of Boolean operations that may be performed by a geometry engine on two geometric areas (A and B) are illustrated in FIGS. 1(a)-1(c). In FIG. 1(a), an And operation is performed on the two geometric regions A and B and the resulting region from this operation is outlined by the thick line. An Or operation is performed on the two geometric regions A and B in FIG. 1(b) with the region resulting from this operation being outlined by the thick line. In FIG. 1(c), an A AndNot B operation is performed on the two geometric regions A and B with the resulting region contained within the thick line.
Some examples of sizing operations that may be performed by geometry engines are illustrated in FIGS. 2(a) and 2(b). In FIG. 2(a), a Grow operation by an amount .DELTA. is performed on the shaded geometric regions so that all of the edges are moved outward by the fixed amount .DELTA. to achieve the geometric region outlined by the thick line. In FIG. 2(b), a Shrink operation is performed on the shaded geometric regions so that all of the edges are moved in by the fixed amount .DELTA. to produce the geometric regions outlined by the thick line. The Grow and Shrink operations are often used in design rule checking for the integrated circuit design to determine whether two or more geometric regions are properly spaced within the design rules.
Geometry engine systems having representations of various bases are known and include geometric based representations by contiguous polygons as illustrated in FIGS. 3(a) and 3(b), geometric based representations by non-overlapping quadrilaterals (rectangles or trapezoids) as illustrated in FIGS. 3(c) and 3(d) and geometric based representations by vertices as illustrated in FIGS. 3(e) and 3(f). While these known representations have been used in integrated circuit design with success, drawbacks and problems are associated with each representation. For example, geometric based representations by contiguous polygons create memory and speed problems because awkward representations typically result which are cumbersome to manipulate. The geometric based representations by non-overlapping quadrilaterals introduce false edges where non-overlapping quadrilaterals are joined together which also generate awkward representations. The known geometric based representations by vertices create problems due to large memory requirements and generally slow processing speeds. Although a potential problem of geometric based representations by vertices is that these representations are not well suited to arbitrary-angle geometries, this does not present a problem in many integrated circuit design applications because integrated circuit designers typically design at right angles to avoid arbitrary angle geometries which simplifies the design and optimizes some photolithography processes.
Of these known representations, the vertex based representation systems generally provide the most advantages for integrated circuit design applications. One such advantage provided by vertex based representations is that simple and consistent data types may be used. For instance, 16 possible data combinations in each quadrant for a vertex may be reduced to 10 possible data combinations for analysis purposes. These 10 possible combinations are illustrated in FIGS. 4(a)-4(j) and include the four concave placements of data at a vertex (FIGS. 4(a)-4(d)), the four convex placements of data at a vertex (FIGS. 4(e)-4(h)), and the two opposed data placements at a vertex (FIGS. 4(i) and 4(j)) which are termed complex placements. Another advantage of the vertex based representation is that no false features of the geometry are generated. An absence of false features allows less memory and processing time to be used as compared to the geometric based representation by quadrilaterals which generates extra construction lines for edges that do not exist. As a result, less processing time and memory space is needed for performing basic routines with vertex representations by avoiding such construction lines. Processing by vertex based representations also generates straightforward inter-geometry interactions so that less processing time of basic routines is necessary in comparison to polygon based representations where complex and multiple figures are used which leads to complex geometric interactions. Vertex based representations also allow routines and operations to be easily performed at the corner represented by the vertex.
Nevertheless, known vertex based representation systems are disadvantageous in certain aspects of integrated circuit design applications. Even though the vertex based representation systems are poorly suited to arbitrary angle geometries this is generally not a great concern in integrated circuit design because the industry generally trends towards right angle designs to provide the best photolithographic resolution between horizontal and vertical edges for certain photolithography processes and simplicity because most geometry is machine-generated. Thereby, the main disadvantage in the known vertex based representation systems are speed and size deficiencies. In other words, the known vertex based representation systems use a large amount of memory for intermediate results and unnecessary processing which lead to systems functioning at slow speeds due to the memory manipulation.
One example of a known vertex based geometry engine system is called the "fang" system and was developed in the mid-1980s by Peter Moore at the University of California--Berkeley, no publications of this system are known except for source code and pseudo code developed therefrom. Due to this lack of published documents, a general description of the fang system will follow. FIG. 5 illustrates some examples of fang data structures. The fang data structure includes a fang geometry data structure 520 which includes "sorted" and "reduced" flag bits 522 and 524. Even though the term "merged" is typically used in fang, the term "reduced" is used instead of merged herein, for term consistency. The sorted flag bits 522 indicate whether a vertex list 526 of the vertices is sorted and the reduced flag bit 524 indicate whether the geometry vertices are reduced (whether there are no self-overlaps of geometry).
The example of FIG. 5 illustrates two vertices 530 and 540 in a linked vertex list. The fields for the vertices 530 and 540 include next pointers 532 and 542, which point to the succeeding entry in the linked list, vertex type fields 534 and 544, and x and y values 536, 538 and 546, 548. In the fang system, vertex sorting is performed in a scan line order from left to right and bottom to top. When a new geometry figure is added by reading or collecting the additional geometry, vertices may become out of order because the new vertices are simply appended to the vertex list. Also, when operations such as growing, mirroring, or rotating are performed, the vertices move in different directions which may cause the vertices in the vertex list 526 to become out of order. Accordingly, the vertex list 526 is sorted automatically by the fang system when needed to ensure that the vertices do not become out of order. In the fang system, the vertex list 526 is sorted very frequently and, since the number of operations required in each sort can be expressed as being of order n log.sub.2 n, or "O(n log.sub.2 n)", wherein n is the number of vertices in the list, these operations may use a substantial amount of time.
An important operation in the fang system is reduction. A short description of geometry "depth" will follow as background for the reduction operation. Generally, the geometry depth is the number of overlapping pieces of geometry at a particular point. For instance, a geometry depth of zero indicates that there is a space between geometric figures and no geometry exists at that point. A geometry depth of one indicates that a geometry figure exists at that point and, in general, the value of the geometry depth corresponds to the number of figures overlapping at a point. The geometry depth concept is used in the reduction operation by the fact that a geometry is reduced when the geometry depth is either zero or one throughout the geometry. A geometry will typically be left unreduced after a new geometric figure has been added which overlaps the existing geometry. Therefore, when a new geometric figure is added, the fang system assumes that overlaps have occurred and clears the reduced flag. Similarly, for Grow and Or operations, two geometric figures may overlap and to ensure that the geometry will be reduced, the fang system clears the reduced flag. When an operation requiring reduced geometry is performed, the reduced flag is analyzed and a reduction operation is performed if the reduced flag is not set.
The reduction method of the fang system will be discussed in more detail with reference to FIG. 6. In the fang system, vertices are examined in a scan line order and a temporary list of vertical edges cutting the current scan line is created and maintained during the reduction operation. In the reduction method of the fang system, points are analyzed where a vertex exists in the input geometry or a vertical edge intersects a scan line containing an input vertex. These are the points labeled a-j in FIG. 6. At each of these analyzed points, the geometry depth to the left of the analyzed point (above and below) is known, the vertex (if present) adds offset to the geometry depth to the above-right of the point, and the edge (if present) adds offset to the geometry depths to the right (both above and below) the point. As a result, an output vertex is produced depending on the geometry depth in each quadrant and the edge is added or removed based on the geometry depth .DELTA. above the point (the depth difference between the regions to the upper right and upper left).
A discussion for one example of this reduction method follows for the points a-j of FIG. 6. At point a, a left edge is added to the edge list and an output vertex is created; at point b, a right edge is added to the edge list and an output vertex is created; at point c, a left edge is noticed and no action is performed; at point d, a left edge is added to the edge list and no output vertex is created; at point e, a right edge is noticed and an output vertex is created; at point f, a right edge is added to the edge list and an output vertex is created; at point g, a left edge is removed from the edge list and an output vertex is created; at point h, a left edge is removed from the edge list and no output vertex is created; at point i, a right edge is removed from the edge list and no output vertex is created; and at point j, a right edge is removed from the edge list and an output vertex is created. By these actions, the geometry illustrated in FIG. 6 is reduced to a geometry depth of zero or one throughout. In the fang system, the geometry is frequently reduced and unnecessary reduction operations may be performed which slows the speed of the system. For example, the fang system may unnecessarily reduce the result of an And operation which feeds another And operation. In the worst case, each reduction takes O(n.sup.2) time but in practice, the number of operations is closer to being linear, O(n).
In known vertex based geometry systems, the memory size necessary to process the geometry is generally considered to be the biggest problem. In the fang system for instance, 16 or 20 bytes of data are used to represent each vertex, which requires a large amount of memory. Fang also requires the memory to be simultaneously used for the complete source data and result of each operation, which leads to a large amount of memory being used. Accordingly, the present invention is primarily directed to reducing the amount of memory necessary for performing the routines. Secondarily, and as a by-product of reducing the memory size, the present invention is also directed to increasing the speed for performing these routines.